package main

import (
	"bufio"
	"fmt"
	"io"
	"math/rand"
	"os"
	"strconv"
	"strings"
	"time"
)

// 可排序双向链表
type SortedDoublyLinkedList struct {
	head *Node
	tail *Node
}

// 链表头部添加元素
func (list *SortedDoublyLinkedList) OfferFirst(e interface{}) {

	node := &Node{
		e:    e,
		prev: nil,
		next: nil,
	}

	head := list.head

	head.next.prev = node
	node.next = head.next
	node.prev = head
	head.next = node
}

// 链表尾部追加元素
func (list *SortedDoublyLinkedList) OfferLast(e interface{}) {

	node := &Node{
		e:    e,
		prev: nil,
		next: nil,
	}

	tail := list.tail

	tail.prev.next = node
	node.prev = tail.prev
	node.next = tail
	tail.prev = node
}

// 获取头部元素
func (list *SortedDoublyLinkedList) PeekFirst() (e interface{}) {

	head := list.head

	if head.next == list.tail {
		return nil
	}

	return head.next.e
}

// 获取尾部元素
func (list *SortedDoublyLinkedList) PeekLast() (e interface{}) {

	tail := list.tail

	if tail.prev == list.head {
		return nil
	}

	return tail.prev.e
}

// 获取并移除头部元素
func (list *SortedDoublyLinkedList) PollFirst() (r interface{}) {

	head := list.head

	if head.next == list.tail {
		return nil
	}

	node := head.next

	e := node.e

	head.next = node.next
	node.next.prev = head

	return e
}

// 获取并移除尾部元素
func (list *SortedDoublyLinkedList) PollLast() (r interface{}) {

	tail := list.tail

	if tail.prev == list.head {
		return nil
	}

	node := tail.prev

	e := node.e

	tail.prev = node.prev
	node.prev.next = tail

	return e
}

// 向链表添加元素，使用comparator作为比较器判断插入位置
func (list *SortedDoublyLinkedList) Add(
	e interface{},
	comparator func(e1 interface{}, e2 interface{}) int) {

	node := &Node{e, nil, nil}

	tmp := list.head.next

	for {
		if tmp == list.tail || comparator(tmp.e, e) > 0 {
			break
		}
		tmp = tmp.next
	}

	node.next = tmp
	node.prev = tmp.prev
	tmp.prev.next = node
	tmp.prev = node
}

// 从链表删除元素，使用comparator作为比较器判断元素相等
func (list *SortedDoublyLinkedList) Delete(
	e interface{},
	comparator func(e1 interface{}, e2 interface{}) int) (r interface{}) {

	head := list.head

	if head.next == list.tail {
		return nil
	}

	tmp := list.head.next

	for {
		if tmp == list.tail || comparator(tmp.e, e) == 0 {
			break
		}
		tmp = tmp.next
	}

	if tmp == list.tail {
		return nil
	}

	tmp.prev.next = tmp.next
	tmp.next.prev = tmp.prev

	return tmp.e
}

// 覆盖String方法，格式化输出
func (list SortedDoublyLinkedList) String() string {
	next := list.head.next
	// 空链表
	if next == list.tail {
		return "[]"
	} else {
		s := "["
		tmp := list.head.next
		for {
			s += fmt.Sprintf("%v, ", tmp.e)
			if tmp.next == list.tail {
				break
			}
			tmp = tmp.next
		}
		return strings.TrimRight(strings.TrimSpace(s), ",") + "]"
	}
}

// 获取正向迭代器
func (list *SortedDoublyLinkedList) Iterate() *AscDoublyLinkedListIterator {
	return &AscDoublyLinkedListIterator{
		current: list.head,
		tail:    list.tail,
	}
}

// 获取反向迭代器
func (list *SortedDoublyLinkedList) DescIterate() *DescDoublyLinkedListIterator {
	return &DescDoublyLinkedListIterator{
		current: list.tail,
		head:    list.head,
	}
}

// 表示一个链表节点
type Node struct {
	e    interface{}
	prev *Node
	next *Node
}

// 迭代器
type Iterator interface {
	HasNext() bool
	Next() interface{}
}

// 双向链表正向迭代器
type AscDoublyLinkedListIterator struct {
	current *Node
	tail    *Node
}

func (iter *AscDoublyLinkedListIterator) HasNext() bool {
	return iter.current.next != iter.tail
}

func (iter *AscDoublyLinkedListIterator) Next() interface{} {

	node := iter.current.next

	if node == iter.tail {
		return nil
	}

	e := node.e
	iter.current = node
	return e
}

// 双向链表反向迭代器
type DescDoublyLinkedListIterator struct {
	current *Node
	head    *Node
}

func (iter *DescDoublyLinkedListIterator) HasNext() bool {
	return iter.current.prev != iter.head
}

func (iter *DescDoublyLinkedListIterator) Next() interface{} {

	node := iter.current.prev

	if node == iter.head {
		return nil
	}

	e := node.e
	iter.current = node
	return e
}

// 示例元素结构体
type Student struct {
	id       int
	name     string
	nickname string
	star     string
}

// 覆盖String方法，格式化输出
func (student *Student) String() string {
	return fmt.Sprintf("{id=%d, name=%s, nickname=%s, star=%s}", student.id, student.name, student.nickname, student.star)
}

// 读取108将
func read108() (arr []*Student) {

	arr = make([]*Student, 108)

	// 打开文件
	file, err := os.Open("D:\\IdeaProjects\\go-study\\basic-go\\src\\list-demo\\sorted-doubly-linked-list\\108.txt")

	if err != nil {
		fmt.Printf("Open file error: %v\n", err)
		return
	}

	defer file.Close()

	// 创建reader
	reader := bufio.NewReader(file)

	i := 0

	// 读取文件内容
	for {

		line, err := reader.ReadString('\n')

		if err == io.EOF {
			break
		}

		line = strings.TrimRight(line, "\r\n")
		fields := strings.Split(line, "\t")
		id, _ := strconv.Atoi(fields[0])
		arr[i] = &Student{
			id:       id,
			name:     fields[3],
			nickname: fields[2],
			star:     fields[1],
		}
		i++
	}

	return arr
}

func main() {

	var f = func(e1 interface{}, e2 interface{}) int {
		return e1.(*Student).id - e2.(*Student).id
	}

	head := &Node{}
	tail := &Node{}

	head.next = tail
	tail.prev = head

	list := &SortedDoublyLinkedList{
		head: head,
		tail: tail,
	}

	// 创建元素
	//s0 := &Student{0, "晁盖", "托塔天王", ""}
	//s1 := &Student{1, "宋江", "及时雨", ""}
	//s2 := &Student{2, "卢俊义", "玉麒麟", ""}
	//s3 := &Student{3, "吴用", "智多星", ""}
	//s14 := &Student{14, "武松", "行者", ""}
	//s10 := &Student{10, "柴进", "小旋风", ""}
	//s13 := &Student{13, "鲁智深", "花和尚", ""}
	//s22 := &Student{22, "李逵", "黑旋风", ""}
	s22x := &Student{22, "李鬼", "黑旋风", "未知"}

	// 读取108将
	students := read108()

	studentMap := make(map[*Student]int, 108)

	for _, student := range students {
		studentMap[student] = 1
	}

	rand.Seed(time.Now().UnixNano())
	index := rand.Intn(108) + 1

	i := 1

	for k, _ := range studentMap {
		if i == index {
			fmt.Printf("测试随机插入: %d\n", i)
			list.Add(s22x, f)
		}
		list.Add(k, f)
		i++
	}

	// 正向迭代
	printList(list)

	fmt.Println("---")

	// 移除
	r := list.Delete(&Student{id: 0}, f)
	fmt.Printf("移除元素: %v\n", r)
	r = list.Delete(&Student{id: 1}, f)
	fmt.Printf("移除元素: %v\n", r)
	r = list.Delete(&Student{id: 10}, f)
	fmt.Printf("移除元素: %v\n", r)
	r = list.Delete(&Student{id: 108}, f)
	fmt.Printf("移除元素: %v\n", r)
	r = list.Delete(&Student{id: 109}, f)
	fmt.Printf("移除元素: %v\n", r)

	// 正向迭代
	printList(list)
}

func printList(list *SortedDoublyLinkedList) {
	iterate := list.Iterate()
	for {
		hasNext := iterate.HasNext()
		if !hasNext {
			break
		}
		e := iterate.Next()
		fmt.Printf("正向迭代元素: %v\n", e)
	}
}
